package ai.zixing.mashibing.basic_class.class12;

/**
 * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。
 */
public class Code01_RobotWalk {

    public static int ways(int N, int M, int K, int P) {
        // 参数无效返回 0
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        // 有 N 个位置， 从 M 出发，还剩 K 步，到达 P 的方法数
        return walk(N, M, K, P);
    }

    // N : 位置位 1 ~ N,固定参数
    // cur : 当前的位置， 可变参数
    // rest : 剩余可以走 rest 步
    // P : 目标位置，固定参数
    public static int walk(int N, int cur, int rest, int P) {
        // 如果美欧剩余步数，当前 cur 位置就是最后的位置
        // 如果最后停在了 P 上，则之前的移动是有效的
        // 如果没有停在 P 上，之前的移动是无效的
        if (rest == 0) {
            // cur == P 表示之前做过的决定
            return cur == P ? 1 : 0;
        }
        // 如果还有移动步数，而且移动到了1，只能从 1 移动到 2
        // 后续还可以走 rest - 1 步
        if (cur == 1) {
            return walk(N, 2, rest - 1, P);
        }
        // 如果还有移动步数，而且移动到了N，只能从 N 移动到 N - 1
        // 后续还可以走 rest - 1 步
        if (cur == N) {
            return walk(N, N - 1, rest - 1, P);
        }
        // 如果还有rest步要走，而当前的cur位置在中间位置上，那么当前这步可以走向左，也可以走向右
        // 走向左之后，后续的过程就是，来到cur-1位置上，还剩rest-1步要走
        // 走向右之后，后续的过程就是，来到cur+1位置上，还剩rest-1步要走
        // 走向左、走向右是截然不同的方法，所以总方法数要都算上
        return walk(N, cur + 1, rest - 1, P) + walk(N, cur - 1, rest - 1, P);
    }

    /**
     * 动态规划——记忆化搜索
     */
    public static int waysCache(int N, int M, int K, int P) {
        if (N < 2 || K < 1 || M < 1 || M > N || P < 1 || P > N) {
            return 0;
        }
        // 到 N 的位置后还剩余 K 步，记录
        int[][] dp = new int[N + 1][K + 1];
        // 初始化记录表， -1 表示初始化状态
        for (int row = 0; row <= N; row++) {
            for (int col = 0; col <= K; col++) {
                dp[row][col] = -1;
            }
        }
        return walkCache(N, M, K, P, dp);
    }

    private static int walkCache(int N, int cur, int rest, int P, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        if (rest == 0) {
            dp[cur][rest] = cur == P ? 1 : 0;
            return dp[cur][rest];
        }
        if (cur == 1) {
            dp[cur][rest] = walkCache(N, 2, rest - 1, P, dp);
            return dp[cur][rest];
        }
        if (cur == N) {
            dp[cur][rest] = walkCache(N, N - 1, rest - 1, P, dp);
            return dp[cur][rest];
        }
        dp[cur][rest] = walkCache(N, cur + 1, rest - 1, P, dp)
                + walkCache(N, cur - 1, rest - 1, P, dp);
        return dp[cur][rest];
    }
}
